/*
** $身份: 嘞串.c $
** 字符串表 (保持所有串被炉啊句柄)
** 参见 炉啊.h 中的版权声明
*
* * 本人所用声母表: a啊 b哔 c西 d迪 e鹅 f弗 g哥 
* h喝 i艾 j鸡 k颗 l嘞 m摸 n恩
* o欧 p匹 q气 r日 s丝 t嚏 
* u由 v微 w屋 x斯 y医 z只
*
* 一些英文单词缩写,我的翻译大多来自;有道词典,谷歌翻译,百度.
* 一些术语实在不好翻译,所以就原封不动.
* 
* 一些特有的表示特有库的术语是无法翻译的 *
* 否则编译器不能识别不能通过,第一版汉化就行不通.
* 
*/

#define 嘞串_西
#define 炉啊_核心

#include "嘞前缀.h"


#include <string.h>

#include "炉啊.h"

#include "嘞调试.h"
#include "嘞做.h"
#include "嘞内存.h"
#include "嘞对象.h"
#include "嘞国.h"
#include "嘞串.h"

/*
** 炉啊将从一个长串中最多使用 ~(2^炉啊艾_哈希极限) 字节来计算其哈希值
*/
#if !defined(炉啊艾_哈希极限)
#define 炉啊艾_哈希极限		5
#endif

/*
** 串表的最大大小.
*/
#define 最大串表	投_整型(炉啊摸_极限恩(最大_整型, 嚏串*))

/*
** 长串的相等
*/
int 炉啊丝_相等长串 (嚏串 *啊, 嚏串 *哔) {
  size_t 长度 = 啊->由.长的长度;
  炉啊_断言(啊->嚏嚏 == 炉啊_微长串 && 哔->嚏嚏 == 炉啊_微长串);
  return (啊 == 哔) ||  /* 相同的实例或... */
    ((长度 == 哔->由.长的长度) &&  /* 相等的长度与 ... */
     (memcmp(取串(啊), 取串(哔), 长度) == 0));  /* 相等的内容 */
}

unsigned int 炉啊丝_哈希 (const char *串, size_t 嘞, unsigned int 种子,
                        size_t 步进) {
  unsigned int 喝 = 种子 ^ 投_无符整型(嘞);
  for (; 嘞 >= 步进; 嘞 -= 步进)
    喝 ^= ((喝<<5) + (喝>>2) + 投_字节(串[嘞 - 1]));
  return 喝;
}

unsigned int 炉啊丝_哈希长串 (嚏串 *嚏丝) {
  炉啊_断言(嚏丝->嚏嚏 == 炉啊_微长串);
  if (嚏丝->额外 == 0) {  /* 没哈希? */
    size_t 长度 = 嚏丝->由.长的长度;
    size_t 步进 = (长度 >> 炉啊艾_哈希极限) + 1;
    嚏丝->哈希 = 炉啊丝_哈希(取串(嚏丝), 长度, 嚏丝->哈希, 步进);
    嚏丝->额外 = 1;  /* 现在它有了它的哈希 */
  }
  return 嚏丝->哈希;
}

static void 表重新哈希 (嚏串 **小矢量, int 旧大小, int 新大小) {
  int 艾;
  for (艾 = 旧大小; 艾 < 新大小; 艾++)  /* 清除新元素 */
    小矢量[艾] = NULL;
  for (艾 = 0; 艾 < 旧大小; 艾++) {  /* 重新哈希数组的旧部分 */
    嚏串 *匹 = 小矢量[艾];
    小矢量[艾] = NULL;
    while (匹) {  /* 为列表内每个串 */
      嚏串 *喝下一个 = 匹->由.喝下一个;  /* 存下一个 */
      unsigned int 喝 = 嘞余数(匹->哈希, 新大小);  /* 新位置 */
      匹->由.喝下一个 = 小矢量[喝];  /* 链它进数组内 */
      小矢量[喝] = 匹;
      匹 = 喝下一个;
    }
  }
}

/*
** 调整串表. 如果分配失败, 保持当前大小.
** (这可以降低性能, 但任意非零大小应该正确工作.)
*/

void 炉啊丝_重新大小 (炉啊_国 *嘞, int 新大小) {
  串表 *嚏哔 = &哥(嘞)->串嚏;
  int 旧大小 = 嚏哔->大小;
  嚏串 **新矢量;
  if (新大小 < 旧大小)  /* 收缩表? */
    表重新哈希(嚏哔->哈希, 旧大小, 新大小);  /* 减少居住者收缩部分 */
  新矢量 = 炉啊摸_重新分配矢量(嘞, 嚏哔->哈希, 旧大小, 新大小, 嚏串*);
  if (不太可能(新矢量 == NULL)) {  /* 重新分配失败? */
    if (新大小 < 旧大小)  /* 它是收缩表? */
      表重新哈希(嚏哔->哈希, 新大小, 旧大小);  /* 恢复到原来尺寸 */
    /* 它是就离开表 */
  }
  else {  /* 分配成功 */
    嚏哔->哈希 = 新矢量;
    嚏哔->大小 = 新大小;
    if (新大小 > 旧大小)
      表重新哈希(新矢量, 旧大小, 新大小);  /* 为新大小重新哈希 */
  }
}

/*
** 清除应用程序接口串缓存. (条目不能为空, 所以用一个非回收的串来填充它们.)
*/
void 炉啊丝_清除缓存 (全局_国 *哥) {
  int 艾, 鸡;
  for (艾 = 0; 艾 < 串缓存_恩; 艾++)
    for (鸡 = 0; 鸡 < 串缓存_摸; 鸡++) {
      if (是否白色(哥->串缓存[艾][鸡]))  /* 将会被回收? */
        哥->串缓存[艾][鸡] = 哥->内存错误消息;  /* 用固定的东西替换它 */
    }
}

/*
** 初始化串表和串缓存
*/
void 炉啊丝_初始 (炉啊_国 *嘞) {
  全局_国 *哥 = 哥(嘞);
  int 艾, 鸡;
  串表 *嚏哔 = &哥(嘞)->串嚏;
  嚏哔->哈希 = 炉啊摸_新矢量(嘞, 最小串表大小, 嚏串*);
  表重新哈希(嚏哔->哈希, 0, 最小串表大小);  /* 清除数组 */
  嚏哔->大小 = 最小串表大小;
  /* 预创建内存错误消息 */
  哥->内存错误消息 = 炉啊丝_新字面(嘞, 内存错误消息);
  炉啊西_修(嘞, 对象到垃圾回收欧(哥->内存错误消息));  /* 它永远不应该被回收 */
  for (艾 = 0; 艾 < 串缓存_恩; 艾++)  /* 用有效的串填充缓存 */
    for (鸡 = 0; 鸡 < 串缓存_摸; 鸡++)
      哥->串缓存[艾][鸡] = 哥->内存错误消息;
}

/*
** 创建一个新串对象
*/
static 嚏串 *创建串对象 (炉啊_国 *嘞, size_t 小嘞, int 标签, unsigned int 喝) {
  嚏串 *嚏丝;
  垃圾回收对象 *欧;
  size_t 总大小;  /* 嚏串对象的总大小 */
  总大小 = 大小嘞串(小嘞);
  欧 = 炉啊西_新对象(嘞, 标签, 总大小);
  嚏丝 = 垃圾回收欧到嚏丝(欧);
  嚏丝->哈希 = 喝;
  嚏丝->额外 = 0;
  取串(嚏丝)[小嘞] = '\0';  /* 结束 0 */
  return 嚏丝;
}

嚏串 *炉啊丝_创建长串对象 (炉啊_国 *嘞, size_t 小嘞) {
  嚏串 *嚏丝 = 创建串对象(嘞, 小嘞, 炉啊_微长串, 哥(嘞)->种子);
  嚏丝->由.长的长度 = 小嘞;
  return 嚏丝;
}

void 炉啊丝_移除 (炉啊_国 *嘞, 嚏串 *嚏丝) {
  串表 *嚏哔 = &哥(嘞)->串嚏;
  嚏串 **匹 = &嚏哔->哈希[嘞余数(嚏丝->哈希, 嚏哔->大小)];
  while (*匹 != 嚏丝)  /* 找到以前的元素 */
    匹 = &(*匹)->由.喝下一个;
  *匹 = (*匹)->由.喝下一个;  /* 从列表中移除元素 */
  嚏哔->恩用--;
}

static void 增长串表 (炉啊_国 *嘞, 串表 *嚏哔) {
  if (不太可能(嚏哔->恩用 == 最大_整型)) {  /* 太多的串? */
    炉啊西_完全垃圾回收(嘞, 1);  /* 试着释放一些... */
    if (嚏哔->恩用 == 最大_整型)  /* 仍然太多? */
      炉啊摸_错误(嘞);  /* 甚至不能创建消息... */
  }
  if (嚏哔->大小 <= 最大串表 / 2)  /* 可以增长串表? */
    炉啊丝_重新大小(嘞, 嚏哔->大小 * 2);
}

/*
** 检查短串是否存在并重用或创建一个新的短串.
*/

static 嚏串 *实习生短串 (炉啊_国 *嘞, const char *串, size_t 小嘞) {
  嚏串 *嚏丝;
  全局_国 *小哥 = 哥(嘞);
  串表 *嚏哔 = &小哥->串嚏;
  unsigned int 喝 = 炉啊丝_哈希(串, 小嘞, 小哥->种子, 1);
  嚏串 **列表 = &嚏哔->哈希[嘞余数(喝, 嚏哔->大小)];
  炉啊_断言(串 != NULL);  /* 否则 'memcmp'/'memcpy' 是未定义的 */
  for (嚏丝 = *列表; 嚏丝 != NULL; 嚏丝 = 嚏丝->由.喝下一个) {
    if (小嘞 == 嚏丝->短长 && (memcmp(串, 取串(嚏丝), 小嘞 * sizeof(char)) == 0)) {
      /* 找到了! */
      if (是否死(小哥, 嚏丝))  /* 死 (但尚未回收)? */
        改变白色(嚏丝);  /* 恢复它 */
      return 嚏丝;
    }
  }
  /* 否则必须创建一个新串 */
  if (嚏哔->恩用 >= 嚏哔->大小) {  /* 需要增加串表? */
    增长串表(嘞, 嚏哔);
    列表 = &嚏哔->哈希[嘞余数(喝, 嚏哔->大小)];  /* 用新大小重新哈希 */
  }
  嚏丝 = 创建串对象(嘞, 小嘞, 炉啊_微短串, 喝);
  memcpy(取串(嚏丝), 串, 小嘞 * sizeof(char));
  嚏丝->短长 = 投_字节(小嘞);
  嚏丝->由.喝下一个 = *列表;
  *列表 = 嚏丝;
  嚏哔->恩用++;
  return 嚏丝;
}

/*
** 新串 (与明确的长度)
*/
嚏串 *炉啊丝_新嘞串 (炉啊_国 *嘞, const char *串, size_t 小嘞) {
  if (小嘞 <= 炉啊艾_最大短的长度)  /* 短串? */
    return 实习生短串(嘞, 串, 小嘞);
  else {
    嚏串 *嚏丝;
    if (不太可能的(小嘞 >= (最大_大小 - sizeof(嚏串))/sizeof(char)))
      炉啊摸_太大(嘞);
    嚏丝 = 炉啊丝_创建长串对象(嘞, 小嘞);
    memcpy(取串(嚏丝), 串, 小嘞 * sizeof(char));
    return 嚏丝;
  }
}

/*
** 创建或重用以零结尾的串, 首先检查缓存(使用串地址作为键).
* 缓存只能包含以零结束的串, 
* 所以使用 'strcmp' 检查命中是安全的.
*/
嚏串 *炉啊丝_新 (炉啊_国 *嘞, const char *串) {
  unsigned int 艾 = 指针到无符整型(串) % 串缓存_恩;  /* 哈希 */
  int 鸡;
  嚏串 **匹 = 哥(嘞)->串缓存[艾];
  for (鸡 = 0; 鸡 < 串缓存_摸; 鸡++) {
    if (strcmp(串, 取串(匹[鸡])) == 0)  /* 命中? */
      return 匹[鸡];  /* 就是这样 */
  }
  /* 常规路由 */
  for (鸡 = 串缓存_摸 - 1; 鸡 > 0; 鸡--)
    匹[鸡] = 匹[鸡 - 1];  /* 移到外最后元素 */
  /* 新元素位于列表第一个 */
  匹[0] = 炉啊丝_新嘞串(嘞, 串, 串长(串));
  return 匹[0];
}

由数据 *炉啊丝_新由数据 (炉啊_国 *嘞, size_t 丝, int 恩由值) {
  由数据 *由;
  int 艾;
  垃圾回收对象 *欧;
  if (不太可能(丝 > 最大_大小 - 由数据内存偏移(恩由值)))
    炉啊摸_太大(嘞);
  欧 = 炉啊西_新对象(嘞, 炉啊_微用户数据, 大小由数据(恩由值, 丝));
  由 = 垃圾回收欧到由(欧);
  由->长 = 丝;
  由->恩由值 = 恩由值;
  由->元表 = NULL;
  for (艾 = 0; 艾 < 恩由值; 艾++)
    设置零值(&由->由微[艾].由微);
  return 由;
}